A binary tree is a tree where every node has two or fewer children. The children are usually called left and right.

  class BinaryTreeNode(object):

    def __init__(self, value):
        self.value = value
        self.left  = None
        self.right = None

This lets us build a structure like this:

That particular example is special because every level of the tree is completely full. There are no "gaps." We call this kind of tree "perfect."

Binary trees have a few interesting properties when they're perfect:

Property 1: the number of total nodes on each "level" doubles as we move down the tree.

Property 2: the number of nodes on the last level is equal to the sum of the number of nodes on all other levels (plus 1). In other words, about half of our nodes are on the last level.

Let's call the number of nodes $n$, and the height of the tree $h$. $h$ can also be thought of as the "number of levels."

If we had $h$, how could we calculate $n$?

Let's just add up the number of nodes on each level! How many nodes are on each level?

If we zero-index the levels, the number of nodes on the $x$th level is exactly $2^x$.

1. Level $0$: $2^0$ nodes,
2. Level $1$: $2^1$ nodes,
3. Level $2$: $2^2$ nodes,
4. Level $3$: $2^3$ nodes,
5. etc

So our total number of nodes is:

Why only up to $2^{h-1}$? Notice that we started counting our levels at 0. So if we have $h$ levels in total, the last level is actually the "$h-1$"-th level. That means the number of nodes on the last level is $2^{h-1}$.

But we can simplify. Property 2 tells us that the number of nodes on the last level is (1 more than) half of the total number of nodes, so we can just take the number of nodes on the last level, multiply it by 2, and subtract 1 to get the number of nodes overall. We know the number of nodes on the last level is $2^{h-1}$, So:

So that's how we can go from $h$ to $n$. What about the other direction?

We need to bring the $h$ down from the exponent. That's what logs are for!

First, some quick review. $\log_{10} (100)$ simply means, "What power must you raise 10 to in order to get 100?". Which is 2, because $10^2 = 100$.

We can use logs in algebra to bring variables down from exponents by exploiting the fact that we can simplify $\log_{10}(10^2)$. What power must we raise $10$ to in order to get $10^2$? That's easy—it's $2$.

So in this case we can take the $\log_{2}$ of both sides:

So that's the relationship between height and total nodes in a perfect binary tree.

Memoization ensures that a function doesn't run for the same inputs more than once by keeping a record of the results for the given inputs (usually in a dictionary).

For example, a simple recursive function for computing the $n$th Fibonacci number:

  def fib(n):
    if n < 0:
        raise IndexError(
            'Index was negative. '
            'No such thing as a negative index in a series.'
        )
    elif n in [0, 1]:
        # Base cases
        return n

    print("computing fib(%i)" % n)
    return fib(n - 1) + fib(n - 2)

Will run on the same inputs multiple times:

  >>> fib(5)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
computing fib(2)
computing fib(3)
computing fib(2)
5

We can imagine the recursive calls of this function as a tree, where the two children of a node are the two recursive calls it makes. We can see that the tree quickly branches out of control:

To avoid the duplicate work caused by the branching, we can wrap the function in a class with an attribute, memo, that maps inputs to outputs. Then we simply

1. check memo to see if we can avoid computing the answer for any given input, and
2. save the results of any calculations to memo.

  class Fibber(object):

    def __init__(self):
        self.memo = {}

    def fib(self, n):
        if n < 0:
            raise IndexError(
                'Index was negative. '
                'No such thing as a negative index in a series.'
            )

        # Base cases
        if n in [0, 1]:
            return n

        # See if we've already calculated this
        if n in self.memo:
            print("grabbing memo[%i]" % n)
            return self.memo[n]

        print("computing fib(%i)" % n)
        result = self.fib(n - 1) + self.fib(n - 2)

        # Memoize
        self.memo[n] = result

        return result

We save a bunch of calls by checking the memo:

  >>> Fibber().fib(5)
computing fib(5)
computing fib(4)
computing fib(3)
computing fib(2)
grabbing memo[2]
grabbing memo[3]
5

Now in our recurrence tree, no node appears more than twice:

Memoization is a common strategy for dynamic programming problems, which are problems where the solution is composed of solutions to the same problem with smaller inputs (as with the Fibonacci problem, above). The other common strategy for dynamic programming problems is going bottom-up, which is usually cleaner and often more efficient.